In order to communicate with a user, a computer must be able to output information to a display. In a graphics system, the display is defined by an array of pixels. For example, in a standard-mode VGA (Video Graphics Adapter) system, the screen is addressed as an array of 640.times.480 pixels. Each pixel on the display may be set to a desired color. The color of each pixel on the screen is stored in a frame buffer. The colors may be directly specified in the frame buffer or specified by reference to a palette which stores color information for a predetermined number of colors. Typically palettes are used for color depths of 16 or 256 colors. When larger color depths are used, such as 32K or 16.7M (true color) color depths, each pixel location in the frame buffer stores data for the RGB (Red, Blue Green) components of each pixel. The number of pixels which may be displayed is defined by the graphic subsystem. Typical VGA modes support 640.times.480, 800.times.600, and 1024.times.768 resolutions. VGA modes with resolution greater than 640.times.480 are generally referred to as "Super VGA". The size of the frame buffer is therefore dependent upon the resolution and color depth of the display.
The speed at which a personal computer operates is dependent upon a number of factors. Naturally, the speed of the microprocessor has a significant influence on the speed of operation of the overall computer system. Next to processor speed, in many cases, the video graphics subsystem has the most influence on the performance of the overall computer system. This is particularly true when a graphical user interface, such as MICROSOFT WINDOWS (by Microsoft Corporation of Redmond, Wash.) is used. In order to boost performance, most modern day personal computers use either a local video bus (which has a higher data bandwidth than the main peripheral bus) and an accelerated graphics card which increases the speed of certain operations. An accelerated graphics card allows the graphics card to perform selected graphics operations at high speed, rather than using the CPU to perform the operation. Hardware acceleration improves the operation of the computer system in two ways: (1) the CPU no longer needs to perform low-level graphics operations handled by the graphics card and (2) the data bandwidth for certain operations is greatly reduced, resulting in less bus traffic.
In order for acceleration to increase the responsiveness of the system, the operating environment, such as WINDOWS, must know the capabilities of the accelerated graphics subsystem. When the operating environment is loaded, it initiates the loading of a graphics driver, which is a program which acts as an intermediary between the operating environment and accelerated graphics hardware (similarly, application software may have their own drivers to take advantage of acceleration features found in an accelerated video card). The driver passes parameters to the operating environment which specify the accelerated capabilities of the graphics subsystem. Thereafter, when the operating environment (or application) needs to perform a graphics operation which could benefit from one of the accelerated capabilities, it passes the necessary data to the driver. The driver interprets the information from the operating environment, processes the information and passes data via the bus to the graphics subsystem. The graphics subsystem then performs the graphics operation by writing data to its frame buffer.
Many of today's application programs are graphics intensive. For example, a computer-aided design program, such as AUTOCAD by AutoDesk, Inc., Sauseleto, Calif., may spend a substantial amount of time drawing a figure to the screen. In some cases, even a small change in the drawing will require the entire drawing to be redrawn. In this case, the ability of the graphics processor to draw lines quickly becomes of critical importance. In addition to the use of line drawing by applications, a graphics card's ability to draw lines may directly affect its other accelerated functions, such as block transfer of data, since the BLT (Bit Block Transfer) engine may use the line draw engine to perform the block transfer.
With regard to line drawing, many problems are addressed in an article "Ambiguity in Incremental Line Rastering", by Jack E. Bresenham, IEEE CG&A, May, 1987, which is incorporated by reference herein. The Bresenham article describes problems in drawing a line using an array of pixels, since lines having real values between two discrete pixels will have to be approximated using one pixel or the other. A speed improvement on this technique involves processing a Bresenham line as a number of segments. This technique is referred to as "run-slice" processing and is described in Jack E. Bresenham, "Run Length Slices for Incremental Lines", IBM Technical Disclosure Bulletin 22-8B, January 1980.
In other applications, manipulation of color information is very important. For example, some applications generate a continuum of colors between two color values (for a line) or three color values (for a triangular region). This operation is commonly referred to as "shading." Typically, the intermediate color values are computed by the CPU, which can significantly affect the responsiveness of the computer system. On the other hand, delegating responsibility of shading functions to the graphics card, while freeing the CPU, can seriously degrade the graphics card's ability to perform other functions.
Further, many programs, including game software, now make use of "three dimensional" (3D) graphics, where color manipulation of objects is used to provide the effect of a three dimensional object on the screen. Calculation of the 3D color information is processor intensive and therefore can significantly affect the responsiveness of the computer system.
While the speed and functionality of graphics cards has been steadily increasing, the demands of software requires even more graphics power. Accordingly, a need has arisen in the industry for a graphics processor which increases the speed at which information is displayed, particularly in connections with line draws, and performs complex graphical operations without requiring additional expensive hardware.